1. Field of the Invention
This invention relates in general to database management systems performed by computers, and in particular, to an effective query transformation technique for queries involving correlated subqueries having correlation join predicates with local filtering predicates involving predicate transitive closure and predicate pullout.
2. Description of Related Art
Computer systems incorporating Relational DataBase Management System (RDBMS) software using Structured Query Language (SQL) interface are well known in the art. The SQL interface has evolved into a standard language for RDBMS software and has been adopted as such by both the American National Standards Institute (ANSI) and the International Standards Organization (ISO).
Most RDBMS software is capable of performing predicate transitive closure optimizations on queries. Existing predicate transitive closure optimizations recognize that a local filtering predicate against a first column of a first table can also be copied, or transitively closed, to a second column of a second table when a join predicate exists on the first and second columns.
Consider the following example query:
SELECT T1.*FROM T1, T2WHERE T1.C1 = T2.C2AND T1.C1 = 1;
In the above example, existing predicate transitive closure optimizations recognize that a local filtering predicate (=1) against a column (C1) on a table (T1) can also be copied, or transitively closed, to another column (C2) on another table (T2) when a join predicate (T1.C1=T2.C2) exists on the column that has the local filtering predicate. Consequently, the above example query can be validly transformed to the following:
SELECT T1.*FROM T1, T2WHERE T1.C1 = T2.C2AND T1.C1 = 1AND T2.C2 = 1;
However, existing predicate transitive closure optimizations cannot work with correlated subqueries. Consider the following example query:
SELECT T1.*FROM T1WHERE EXISTS(SELECT T2.*FROM T2WHERET1.C1 = T2.C2ANDT2.C2 = x);
In the above example query, the correlated subquery (SELECT T2 * . . . ) contains a correlation join predicate (T1.C1=T2.C2) and a local filtering predicate (T2.C2=x). However, a predicate transitive closure optimization cannot be performed on the correlated subquery, using existing techniques. As a result, a selective local predicate that resides within the correlated subquery may not be applied as early as it could be, thereby resulting in inefficient performance. For example, the correlated subquery in the above example is executed once per qualified row generated by the outer SELECT statement, i.e., once for every row in table T1.
With existing RDBMS software, the only solution is to manually transform the query. However, it is unreasonable to expect users to always code queries in most efficient manner. Instead, it is the job of the query optimizer in the RDBMS to transform a query to improve performance.
Consequently, there is a need in the art for an effective query transformation technique for queries involving correlated subqueries having correlation join predicates with local filtering predicates involving predicate transitive closure and predicate pullout.